package tree;

import java.util.HashMap;
import java.util.Map;

/**
 * 题目：实现一个lru缓存
 *
 * @Author Gavin
 * @date 2021.12.27 21:13
 */
public class tree_5 {
    /**
     * lru缓存：尝试用的方式就是链表加hash表
     */
    //head指针指向的是链表的尾部，代表最少访问的那个节点（head.prev表示的就是最新访问的节点）
    private Node head = new Node(-1, -1, null, null);
    private Map<Integer, Node> map = new HashMap<>();

    //定义一个函数，把某个节点移动到head.prev上，表示该节点是最新访问过的节点。
    private void move2Head(Node node) {
        if (node == head) {
            //head指向下一个最少访问的节点上面
            head = head.next;
            return;
        }
        //先断开这个节点
        node.prev.next = node.next;
        node.next.prev = node.prev;
        //拼接到头部（head.next位置）
        node.next = head.next;
        node.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    //构建一个容量为capacity的循环链表
    public void LRUCache(int capacity) {
        Node cur = head;
        for (int i = 0; i < capacity - 1; i++) {
            cur.next = new Node(-1, -1, cur, null);
            cur = cur.next;
        }
        cur.next = head;
        head.prev = cur;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node cur = map.get(key);
        //访问该节点之后就把该节点放到链表的头部后面
        move2Head(cur);
        return cur.val;
    }

    public void put(int key, int val) {
        if (map.containsKey(key)) {
            Node cur = map.get(key);
            cur.val = val;
            move2Head(cur);
        } else {
            //lru的精髓，把最少使用的这个节点移除替换掉，然后放到头节点的上一个
            //此时head代表最少访问的那个节点，直接移除
            if (head.val != -1) map.remove(head.key);
            head.key = key;
            head.val = val;
            map.put(key, head);
            head = head.next;
        }
    }

}

class Node {
    int key, val;
    Node prev, next;

    Node(int key, int val, Node prev, Node next) {
        this.key = key;
        this.val = val;
        this.prev = prev;
        this.next = next;
    }
}
